package fs.math {
	/**
	 * ...
	 * @author flyingSnow
	 */
	public final class FFT {
		
		/**
		 * The Fouier Transform
		 * @param	realArr
		 * @return  {real:resultReal,imag:resultImag };
		 */
		public static function transform(real:Array):Object {			
			var N:uint = real.length;			
			
			var i:int;
			var j:int;
			
			var realTemp:Array=[];
			var resultReal:Array=[];
			var imagTemp:Array=[];
			var resultImag:Array=[];
			var t:Array=[];
			
			var sumReal:Number;
			var sumImag:Number;
			
			var factor:Number = 2 * Math.PI / N;
			
			//补充imaginaryArr长度
			//if (imag == null) {
				//imag = [];
			//}
			//for (var i:int = imag.length; i < real.length;i++ ) {
				//imag.push(0);
			//}				
			
			//开始变换
			var multiI:Number = 0;
			
			for (i = 0; i < N; i++ ) {
				sumReal = sumImag = 0;
				//var multiI:Number = factor * i;
				for (j = 0; j < N; j++ ) {
					t[j] = multiI * j;
					
					realTemp[j] = Math.cos(t[j]) * real[j];
					imagTemp[j] = -Math.sin(t[j]) * real[j];
					
					sumReal += realTemp[j] ;
					sumImag += imagTemp[j];
				}
				
				resultReal[i] =sumReal;
				resultImag[i] = sumImag;
				
				multiI += factor;
			}
			return {real:resultReal,imag:resultImag };
		}
		
		/**
		 * The Inverse Fouier Transform
		 * @param	realArr
		 * @param	imaginaryArr
		 * @return  {real:resultReal,imag:resultImag };
		 */
		public static function InverseTransform(real:Array,imag:Array=null):Object {
			var N:uint = real.length;			
			
			var i:int;
			var j:int;
			
			var realTemp:Array=[];
			var resultReal:Array=[];
			var imagTemp:Array=[];
			var resultImag:Array=[];
			var t:Array=[];
			
			var sumReal:Number;
			var sumImag:Number;
			
			var factor:Number = 2 * Math.PI / N;
			
			//补充imag长度
			if (imag == null) {
				imag = [];
			}
			for (i = imag.length; i < real.length;i++ ) {
				imag.push(0);
			}		
			
			//开始变换
			2 * Math.PI * i * j / N
			var multiI:Number = 0;
			for (i = 0; i < N; i++ ) {
				sumReal = sumImag = 0;
				for (j = 0; j < N; j++ ) {
					t[j] = multiI * j;
					realTemp[j] = real[j] * Math.cos(t[j]) - imag[j] * Math.sin(t[j]);
					imagTemp[j] = real[j] * Math.sin(t[j]) + imag[j] * Math.cos(t[j]);
					
					sumReal += realTemp[j];
					sumImag += imagTemp[j];
				}
				
				resultReal[i] = sumReal / N;
				resultImag[i] = sumImag / N;
				
				multiI += factor;
			}
			
			return {real:resultReal,imag:resultImag };
		}
	}

}